This invention-relates to color image processing, and specifically to color halftoning for digital printing and copying using error diffusion techniques.
Halftoning is a technique whereby a multilevel greyscale or color image may be rendered for a printing or display mechanism that is capable of presenting a reduced number of distinct color levels. Halftoning for target devices where dots are either xe2x80x9conxe2x80x9d or xe2x80x9coffxe2x80x9d is referred to as xe2x80x9cbinary halftoningxe2x80x9d because only two levels of each colorant exist. In monochromatic binary halftoning, the rendered image is represented as a collection of black dots on a white background, with the dots being dense in regions of the image that are dark, and sparse in regions of the image that are light. Conversion of a color or continuous greyscale image into a halftoned image requires that the image be sampled, and that a scheme for converting the continuous sampled information be provided. During this process, unwanted patterns may be generated, which patterns need to be eliminated if the final image is to be an accurate and acceptable representation of the original image.
Error diffusion (ED) techniques have been used in digital printing for many years in an attempt to eliminate digitally generated patterns that are perceptible to the human visual system (HVS), however, the complete elimination of these undesirable artifacts has been a problem and has been the focus of much research. Many of the proposed solutions involve systematically modulating the threshold of the error diffusion process rather than holding it constant for the entire image, in fact, the primary way in which the various proposed solutions differ is in how the threshold is modulated.
A number of electronic halftoning techniques are described in Billotet-Hoffinan et al., On the error diffusion technique for electronic halftoning, Proceedings of the SID, Vol. 24/3, 1983. This paper describes hybrid error diffusion techniques wherein the threshold is modulated according to a dither function. Diamond-shaped, Bayer, and ring-shaped dither functions are used, which resulted in the reduction of tendency of the generation of regular textures following error diffusion.
Robert Ulichney, xe2x80x9cDigital Halftoningxe2x80x9d, MIT Press, 1988, proposes adding random noise to the entire image to defeat the visual artifacts discussed above, however, adding noise, such as the xe2x80x98bluexe2x80x99 noise suggested in the paper, to all parts of an image tends to increase graininess.
U.S. Pat. No. 5,014,333, to Miller et al., for Image processor with smooth transitioning between dither and diffusion processes, granted May 7, 1991, discloses an error-diffusion halftoning method wherein a periodic ordered dither matrix is used to define spatially-varying threshold values. The reference describes attenuating the propagated errors in very light and very dark areas. The magnitude of threshold modulation is based on the content of the original image, and the dither matrices vary with the frequency content of the input image, to effect a smooth transition between dither and diffusion processes.
U.S. Pat. No. 5,150,429 to Miller et al., for Image processor with error diffusion modulated threshold matrix, granted Sep. 2, 1992, discloses another error-diffusion halftoning method wherein the threshold matrix is systematically modulated. In, this case, the threshold-modulating pattern is complementary to the known artifact pattern of error diffusion processes. The reference describes a threshold matrix which has sparse threshold modulations arranged along lines that are approximately orthogonal to the prevailing orientation of the worming patterns.
Eschbach, Error Diffusion Algorithom with Reduced Artifacts, Proceedings of the ISandT, 45th Annual Conference, May 10-15, 1992, pp. 171-173, describes two different error distribution matrices, one for highlights and one for mid-tones, which alleviated the dominant artifacts in each input range. Eschbach asserts that in highlights, the worm-like structures are greatly reduced by means of a modified error-dittusion matrix. Transition artifacts due to switching weight matrices may be avoided by randomizing the location of the transition boundary.
U.S. Pat. No. 5,313,287 to Barton, for Imposed weight matrix error diffusion halftoning of image data, granted May 17, 1994, discloses an error-diffusion halftoning method where the direction of processing scan lines of a source image is selected with blue noise, i.e., such that the direction of processing is biased away from long streaks in the same direction, in order to reduce directional and start-up anomalies. xe2x80x9cSerpentinexe2x80x9d, xe2x80x9cpeanoxe2x80x9d, and other pixel-visitation strategies are also suggested. The pixel values are modified according to a spatially-repeating pattern prior to thresholding. Error diffusion threshold values are modulated with blue noise. Because of the effects of the blue noise, it is possible to distribute the error using a special three-weight filter as opposed to the more traditional larger distribution filters.
U.S. Pat. No. 5,737,453 to Ostromoukhov, for Enhanced error-diffusion method for color or black-and-white reproduction, granted Apr. 7, 1998 describes an error diffusion method in which the threshold is modulated according to a 2D pattern and different diffusion matrices are used for different gray levels. The threshold-modulating pattern is obtained by applying standard error diffusion, with a fixed threshold of 0.5, to a constant gray level image. The constant gray-level image has certain properties, i.e., the gray level is an irrational number, and the resulting threshold-modulating pattern is largely artifact-free.
U.S. Pat. No. 5,809,177 to Metcalfe et al., for Hybrid error diffusion pattern shifting reduction using programmable threshold perturbation, granted Sep. 15, 1998, discloses a method of selectively adding noise based on the input gray level. The input gray signal is modified with either random noise multiplied by a gray-level dependent coefficient or by a predetermined value from a checkerboard or vertical-line pattern. The value from the pattern is dependent upon the gray-level and pixel location of the image data.
The foregoing disclosures illustrate the efforts undertaken to address error diffusion artifacts such as worming. Another category of halftoning techniques is that in which error is not diffused and which incorporates large threshold matrices which are intended to avoid the undesirable patterning of previous xe2x80x9cditheringxe2x80x9d techniques, which is due to the introduction of energy at low-spatial frequencies to which the human visual system is highly sensitive. This technique also manages to achieve acceptable results. The threshold-matrix design process is intended to produce a resultant image which exhibits the characteristics of so-called xe2x80x9cblue noise,xe2x80x9d as described by Ulicheney, supra. Blue noise patterns have been found desirable for halftoning because the human visual system is less sensitive to these spatial frequencies. It will be appreciated by those of skill in the art that error diffusion is also considered to achieve this goal, albeit in a very different way. Screens have been successfully produced having an aperiodic, uncorrelated structure without low frequency graininess.
U.S. Pat. No. 5,341,228 to Parker et al., for Method and apparatus for halftone rendering of a gray scale image using a blue noise mask, granted Aug. 23, 1994, discloses a halftoning screening method that uses a blue noise mask. The mask was constructed using a frequency domain procedure. The procedure involves repeated high-pass filtering and spatial-domain dot swapping.
U.S. Pat. No. 5,535,020 to Ulichney, for Void and cluster apparatus and method for generating dither templates, granted Jul. 9, 1996, discloses a method of generating a blue noise screen that avoids the iterative frequency-domain approach. This technique is based on spatial-domain dot swapping between the largest voids and largest clusters of threshold values.
U.S. Pat. No. 5,673,121 to Wang, for Stochastic halftoning screening method, granted Sep. 30, 1997, discloses a method for optimizing a stochastic screen by iteratively selecting and manipulating pairs of threshold levels in the stochastic screen matrix. The threshold values are swapped in position if it is determined that a swap would improve an objective metric that is based on inter-pixel distance.
U.S. Pat. No. 5,493,416 to Fan, for Method combining error diffusion and traditional halftoning with arbitrary screen orientation, granted Feb. 20, 1996, describes a system that compensates for errors only in critical blocks.
A method for reproducing a gray level image in a reduced medium includes a comparison step, a diffusing step, and determining a threshold value for the comparison step from a matrix of threshold values, wherein the matrix has a spatial-chromatic correlated noise pattern.
An object of the invention is to provide a method of adding correlated chromatic noise which, at a magnitude that may be used for prior art white noise techniques, appears less noisy to the human visual system than the white-noise approach.
A further object of the invention is to provide a noise pattern that is correlated both spatially and across output color-planes to resolve the error diffusion artifact problem and the color clustering problem simultaneously.
Another object of the invention is to provide a method of improving the rendition of highlights by producing more uniform dispersion of color dots forming an output image.
These and other objects and advantages of the invention will become more fully apparent as the description which follows is read in conjunction with the drawings.